1. Field of the Invention
The invention relates to a data compression system which employs an expanding input data window and an additional transformation for the purpose of locating and encoding matching strings of data.
2. Description of Related Art
Data compression is becoming a very important requirement for high speed data transfer. This is especially true where large blocks of data have to be moved as is common when using the information superhighway. A useful survey of modern data compression techniques is found in an article entitled "Putting Data on a Diet" which appeared in the April, 1993 edition of the IEEE Spectrum, pages 36-39.
Many modern data compression techniques are based upon the LZ77 and LZ78 string matching methods invented by A. Lempel and J. Ziv in 1977 and 1978, respectively. LZ77 exploits the fact that words and phrases within a text stream are likely to be repeated. When they do occur, they may be encoded as a pointer to any previous occurrence plus a field indicating the length of the match. When there is no match, an escape bit may be used to indicate that a non-compressed literal character follows. The key to the operation of LZ77 is a sliding history buffer which stores the text most recently transmitted. When the buffer fills up, its oldest contents are discarded. Unfortunately, when data passes out of the sliding history buffer, it is no longer useful. The LZ78 technique attempts to overcome the LZ77 window size limitations by parsing all text seen so far into phrases were each phrase is the longest matching phrase seen previously plus one character. The LZ78 technique is limited by the fact that only a subset of all possible strings seen in the text so far can be encoded and the size of the encoded dictionary is of a fixed size.
The patent prior art discloses interesting compression techniques but none of which achieve the efficiency and transmission speed of the present invention. For example, U.S. Pat. Nos. 4,811,265, 4,890,326, 4,985,700 and 5,363,096 discuss, in other contexts, the combining of two or more values into another value as part of a general data processing scheme. Those values might be combined, for example, by direct multiplication or by vector multiplication or some other mathematical process. The concept of dividing values in a data processing and transmitting context is described in U.S. Pat. No. 4,930,265, among others. Encoding information into the remainder of a mathematical process is generally discussed in U.S. Pat. Nos. 4,122,440 and 5,208,593. The use of subsequent encoding techniques following LZ data compression is mentioned in U.S. Pat. No. 5,374,916.
The following U.S. Patents are believed to be of lesser, but still possible relevance, to the present inventive concepts: 4,701,745; 5,016,009; 5,126,739; 5,140,321; 5,281,967; 5,289,895; 5,309,526 and 5,339,076.
U.S. Pat. No. 5,369,605 entitled INCREMENTAL SEARCH CONTENT ADDRESSABLE MEMORY FOR INCREASED DATA COMPRESSION EFFICIENCY discloses the use of a conventional "sliding window" in the context of LZ77 compression.
Insofar as can be determined there only appears to be one prior art discussion of the concept of an expanding window. This technique known as LZB is briefly described in "Modeling for Text Compression" by T. Bell, J. Cleary and I. Witten. Most LZ77 derived techniques include at least two limitations on the strings which can be encoded first by the number of bytes that are matched and second by distance (e.g., bounded window). That is to say, they refer to a fixed-size sliding window approach. See, for example, the discussion in U.S. Pat. No. 4,701,745.
Insofar as understood, none of the foregoing prior art teaches the present invention which employs an expandable history window and is able to obtain significantly improved compression and transmission speeds not obtainable by other techniques.